Memory Management
Background
⚫
Memory consists of large array of words or bytes, each
with its own address.
⚫
CPU fetches instructions from the memory as per the
value of program counter.
⚫
Memory unit only sees the addresses and is not concerned
with how they are generated
Basic Hardware
⚫
CPU can directly address – Main memory and
registers
⚫
Instructions only take main memory address and
registers as operands
⚫
So the data or any instructions must be in direct
access device to be executed
⚫
CPU can access registers with one clock cycle.
⚫
But main memory access requires many clock cycles.
⚫
Hence cache is used to increase the access rate
Address space of a process
⚫
Base register – holds the
smallest legal physical
address
⚫
Limit register – specifies
the size of the range
Protection
⚫
CPU hardware compares every address generated in user mode.
⚫
Base and limit registers can only be updated by OS in kernel
mode
Address Binding
⚫
Compile time: If memory location known at
compile time, absolute code can be generated;
must recompile code if starting location changes
⚫
Load time: Must generate relocatable code if
memory location is not known at compile time.
In this case final binding is delayed until load
time.
⚫
Execution time: Binding delayed until run time
if the process can be moved during its execution
from one memory segment to another. Need
hardware support for address maps.
Logical vs physical address
⚫
Logical address – generated by the CPU; also referred
to as virtual address
⚫
Physical address – address seen by the memory
management unit
⚫
Compile time and load time address binding generate
identical logical and physical addresses.
⚫
Execution time generates different logical and
physical addresses.
⚫
Memory management unit(MMU) is used to map
logical address to physical address.
Dynamic Loading
⚫
Entire program and its entire data should be in
memory for process to execute.
⚫
Therefore process size <= memory size
Dynamic loading
⚫
Load a routine only when it is called
Swapping
⚫
Used in priority based
scheduling algorithms.
⚫
To make space for
higher priority process.
⚫
Where to swap in the
process?
⚫
Same space
⚫
Different
Memory Allocation Schemes
⚫
Contiguous memory allocation
⚫
Paging
⚫
Segmentation
Contiguous Memory allocation
⚫
Each process is contained in a single contiguous section
of memory.
⚫
Memory mapping and protection
⚫
Relocation register – contains value of smallest physical address
⚫
Limit register – contains the range of logical addresses
Problem
⚫
Suppose that the value of relocation register is 100040
and limit register is 74600. What are the physical
addresses for the following logical addresses?
1.
70000
2.
75000
⚫
Ans:
1. Check whether logical address < limit register value.
70000<74600. TRUE.
Physical address = logical address + relocation register
value
i.e. Physical address = 70000+100040=170040
2. Check whether logical address < limit register value.
75000<74600. FALSE
Trap: addressing error
Contiguous Memory allocation
1. Fixed size partition
⚫
Each partition may
contain exactly one
process.
⚫
Degree of
multiprogramming =
number of partitions
⚫
Used in IBM OS/360
⚫
Not used now
2. Variable partition
scheme
⚫
Partitions of variable
size
⚫
Initially all the memory
is free.
⚫
OS maintains a table
indicating which part
of memory is free.
Fixed partition
Variable partition
P1
P2
P3
P4
p5
0
10
20
30
40
50
60
70
P1
P2
p3
0
20
30
40
70
Variable partition working
⚫
Suppose total memory is 100Mb
Memory Status
0-100 Free
100
0
Variable partition working
⚫
Process P1 requires 10Mb space
Memory Status
0-9 P1
10-100 free
100
0
10
P1
Variable partition working
⚫
Process P2 requires 30Mb space
Memory Status
0-9 P1
10-39 P2
40-100 Free
100
0
10
P1
40
P2
Memory Status
0-9 P1
10-100 free
Variable partition working
⚫
Process P3 requires 20Mb space
Memory Status
0-9 P1
10-39 P2
40-100 Free
100
0
10
P1
40
P2
60
P3
Memory Status
0-9 P1
10-39 P2
40-59 P3
60-100 Free
Variable partition working
⚫
Process P1 finishes its execution.
⚫
So the space is freed
100
0
10
P1
40
P2
60
P3
Memory Status
0-9 P1
10-39 P2
40-59 P3
60-100 Free
Memory Status
0-9 Free
10-39 P2
40-59 P3
60-100 Free
Variable partition working
⚫
Process P4 requires 25 Mb space
100
0
10
40
P2
60
P3
Memory Status
0-9 Free
10-39 P2
40-59 P3
60-100 Free
85
P4
Memory Status
0-9 Free
10-39 P2
40-59 P3
60-84 P4
85-100 Free
Variable partition working
⚫
Process P3 finishes its execution.
⚫
So the space is freed
100
0
10
40
P2
60
P3
Memory Status
0-9 Free
10-39 P2
40-59 P3
60-84 P4
85-100 Free
85
P4
Memory Status
0-9 Free
10-39 P2
40-59 Free
60-84 P4
85-100 Free
Variable partition working
⚫
Process P5 requires 25 Mb space
⚫
Can it be granted?
100
0
10
40
P2
60
85
P4
Memory Status
0-9 Free
10-39 P2
40-59 Free
60-84 P4
85-100 Free
10
Mb
free
20
Mb
free
16
Mb
free
Total free space = 10+20+16=46Mb
No, because 25Mb is not free in a single slot(hole)
This problem
is called
“External
Fragmentation”
External Fragmentation
⚫
When there is enough total memory space to satisfy a
request, but the available space is not contiguous.
⚫
Solution
⚫
Compaction – shuffle the memory contents so as to
place all free memory together in one large block.
⚫
First fit – allocate the first hole that is big enough
⚫
Best fit – allocate the smallest hole that is big enough
⚫
Worst fit – allocate the largest hole
Block(hole) allocation
Block(hole) allocation- Example
⚫
Given three free memory
partitions of 10 KB, 20 KB
and 15 KB(in order), how
would each of the first-fit,
best-fit, and worst-fit
algorithms place processes
of 15 KB, 10 KB, 20 KB and
5 KB (in order)?
99
10
40
60
85
0
Block(hole) allocation- Example
⚫
15 KB, 10 KB, 20 KB and 5 KB (in order)
99
10
40
P2
60
85
P4
0
99
10
40
P2
60
85
P4
0
99
10
40
P2
60
85
P4
0
First fit
Best fit
Worst fit
15KB
15kb
55
15kb
15kb
55
10KB
10kb 10kb
10kb
95
20KB
20kb
5KB
5kb
5kb
5
Practice Problem
⚫
Given four free memory partitions of 150 KB, 200 KB , 100 KB and 50
KB(in order), how would each of the first-fit, best-fit, and worst-fit
algorithms place processes of 150 KB, 100 KB, 200 KB and 50 KB (in
order)? Which algorithm performs the best?
100
250
400
700
0
First fit
600
800
850
900
150kb
100kb
50kb
500
550
100
250
400
700
0
Best fit
600
800
850
900
150kb
100kb
50kb
200kb
100
250
400
700
0
Worst fit
600
800
850
900
150kb
100kb
50kb
750
200
550
Paging
⚫
Physical address space of a process is non-
contiguous.
⚫
Implementation
⚫
Frames – fixed size blocks of physical memory
⚫
Pages – fixed size slots of logical memory
⚫
When a process is to be executed, its pages are loaded
into any available memory frames from the backing
store.
⚫
Page Table – to translate logical address to physical
address
Address Translation
⚫
Address generated by CPU is divided into:
⚫
Page number (p) – used as an index into a page table which contains base
address of each page in physical memory
⚫
Page offset (d) – combined with base address to define the physical
memory address that is sent to the memory unit
Address Translation
Address Translation
⚫
How to break logical address into page number and
page offset?
If address space size = 2
m
Page size = 2
n
Then
Page number = higher order (m-n) bits
Page offset = n low-order bits
p d
page number page offset
n
m-n
Example
Q. Using a page size of 4bytes and physical
memory of 32 bytes, find the physical
address if the logical address is
a) 4
b) 10
Solution:
a) Page size = 4bytes = 2
2
(i.e. n=2)
Address space = 32 = 2
5
(i.e. m=5)
Logical address = 4
In binary = 00100
Page number=(higher)(m-n)bits=5-2=3 bits
i.e. 001 = 1
Offset = (lower)n bits = 2 bits i.e. 00 = 0
From page table, if page number = 1
Then frame = 6
Physical address = frame*page size+offset
= 6*4+0 = 24
Frame allocation
Before allocation After allocation
Hardware Support
Problem
Q. If it takes 20 nanoseconds to search the TLB , 100
nanoseconds for PT and 100 nanoseconds to access memory,
then find the effective access time if the hit-ratio is 80%.
Solution:
Time taken to access data if page is found in TLB =
20+100=120
Time taken to access data if page is not found in TLB =
20+100+100 = 220
Effective access time = .80*120 + .20*220
= 140 nanoseconds
Problem
Q. If it takes 20 nanoseconds to search the TLB and
100 nanoseconds to access memory, then find the
effective access time if the miss-ratio is 2%.
Solution:
Effective access time = .98*120 + .02*220
= 122 nanoseconds
Memory Protection
⚫
Memory protection implemented by associating protection bit with each
frame
⚫
Valid-invalid bit attached to each entry in the page table:
⚫
“valid” indicates that the associated page is in the process’ logical address
space, and is thus a legal page
⚫
“invalid” indicates that the page is not in the process’ logical address space
Shared Page tables
Segmentation
⚫
Users view memory as a collection of variable size
segments. With no necessary ordering of these segments
⚫
Segmentation is memory-management scheme that
supports user view of memory
⚫
A program is a collection of segments. A segment is a
logical unit such as:
main program, procedure,
function, method,
object, local variables, global variables,
common block, stack,
symbol table, arrays
User’s view of a program
Segmentation hardware
⚫
Each segment has a name and its length.
⚫
Logical address consists of a two tuple:
<segment-number, offset>,
⚫
Segment table – maps two-dimensional physical addresses; each table entry
has:
⚫
base – contains the starting physical address where the segments reside in
memory
⚫
limit – specifies the length of the segment
⚫
Segment-table base register (STBR) points to the segment table’s location in
memory
⚫
Segment-table length register (STLR) indicates number of segments used by a
program;
segment number s is legal if s < STLR
Example
⚫
Segment 2 is 400 bytes long and begins at location 4300.
⚫
Thus a reference to byte 53 of segment 2 is mapped onto
location 4300+53=4353.
Problem
Q. What is the physical address if the byte is 852 of
segment 3?
Ans:
3200+852=4052.
Q. What is the physical address if the byte is 1222 of
segment 0 ?
Ans: Would result in a trap to OS, as this segment
is only 1000 bytes long.
9.1
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
CH 9: VIRTUAL MEMORY
● Virtual memory – is a technique that allows execution of
processes that are not completely in memory. One of the major
advantage of this scheme is that programs can be larger than the
physical memory available.
● separation of user logical memory from physical memory.
● Program would no longer be constrained by the amount of physical
memory that is available.
● Bcz each program takes less space, more program could be run at
the same time.
● Less I/O would be needed to load or swap each user program into
memory, Virtual memory can be implemented via:
● Demand paging
● Demand segmentation
9.2
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Transfer of a Paged Memory to Contiguous Disk Space
9.3
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Demand Paging
● Bring a page into memory only when it is needed
● Less I/O needed
● Less memory needed
● Faster response
● More users
● Page is needed
⇒
reference to it
● not-in-memory
⇒
bring to memory
● Lazy swapper – never swaps a page into memory unless
page will be needed
● Swapper that deals with pages is a pager
9.4
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Valid-Invalid Bit
●
With each page table entry a valid–invalid bit is associated
(v
⇒
in-memory, i
⇒
not-in-memory)
● Initially valid–invalid bit is set to i on all entries
● Example of a page table snapshot:
● During address translation, if valid–invalid bit in page table entry
is I
⇒
page fault
v
v
v
v
i
i
i
…
.
Frame
#
valid-invalid
bit
page
table
9.5
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Page Table When Some Pages Are Not in Main Memory
9.6
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Page Fault
●
If there is a reference to a page, first reference
to that page will trap to operating system:
page fault
1.
Get empty frame
2.
Swap page into frame
3.
Reset tables
4.
Set validation bit = v
5.
Restart the instruction that caused the page fault
9.7
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Steps in Handling a Page Fault
9.8
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
What happens if there is no free frame?
●
Page replacement – find a page in memory and swap it out
●
Replacement algorithm selects the victim page
●
want an algorithm which will result in minimum number
of page faults
9.9
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Basic Page Replacement
1.
Find the location of the desired page on disk
2.
Find a free frame:
- If there is a free frame, then use it
- If there are no free frames, use a page replacement
algorithm to select a victim frame
3.
Bring the desired page into the (newly) freed frame, and
update the page and frame tables
4.
Restart the interrupted instruction of the process
9.10
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Page Replacement
●
Use modify (dirty) bit to reduce overhead of page transfers
● If victim page is unmodified, then no need to write it back to
disk
9.11
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Page Replacement Algorithms
●
Want lowest page-fault rate
●
Subsequently low page-fault service time too
●
Evaluate algorithm by running it on a particular fixed
string of memory references (reference string) and
computing the number of page faults on that string
●
FIFO page replacement
●
Optimal page replacement
●
LRU page replacement
9.12
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
FIFO Page Replacement
9.13
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Graph of Page Faults vs Number of Frames
Expected behavior of a good page replacement
algorithm.
9.14
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
First-In-First-Out (FIFO) Algorithm
●
Reference string (12 total refs / 5 unique): 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
●
3 frames (3 pages can be in memory per process)
● 4 frames (3 pages can be in memory per process)
● Belady’s Anomaly: More frames may yield more page faults
1
2
3
1
2
3
4
1
2
5
3
4
9 page
faults
1
2
3
1
2
3
5
1
2
4
5
10 page
faults
4
4 3
9.15
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
FIFO Illustration of Belady’s Anomaly
9.16
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Optimal Algorithm (Called OPT or MIN)
●
Replace page that will not be used for longest period of time
● 4 frames example
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
●
How do we know which page will be used latest?
●
We don’t! OPT is impossible to implement accurately unless
the order of page references is known a priori
1
2
3
4
6 page
faults
4
5
9.17
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Reference to page 2 replaces page 7, because page 7 will not be
used until reference 18, whereas page 0 will be used at 5, and
page 1 at 14.
The reference to page 3 replaces page 1, as page 1 will be the
last of the 3 pages in the memory to be referenced again.
With only 9 page faults, OPT is much better than FIFO algo.
Which results in 15 faults.
9.18
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
LRU replacement
● The key distinction between FIFO and OPT(other than
looking backward versus forward in time) is that FIFO algo
uses the time when a page was brought into the memory
whereas Opt algo uses the time when a page is to be used.
● If we use recent past as an approximation of the near
future, thus we can replace a page that has not been used
for the longest period of time.
● This approach is LEAST RECENTLY USED(LRU) algorithm.
● LRU replacement associates with each page the time of
the page’s last use. When a page is to be replaced, LRU
chooses the page that has not been used for the longest
period of time.
9.19
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Least Recently Used (LRU) Algorithm
●
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
●
Considered good, but difficult to implement
●
LRU does not suffer from Belady’s anomaly
5
2
4
3
1
2
3
4
1
2
5
4
1
2
5
3
1
2
4
3
9.20
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
LRU Page Replacement
9.21
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Thrashing
●
If the number of frames allocated to a low priority process falls
below the minimum number required by the computer
architecture , If a process does not have “enough” pages in
memory, it will quickly page fault at this point it must replace
some page. Since all the pages are active in use, it must replace
a page that will be needed again right away. Consequently, it
page faults again, and again and again…. the page-fault rate can
be very high. This leads to:
●
Low CPU utilization and low throughput
●
OS attempts to increase the degree of multiprogramming
●
Another process added to the system
●
Even more page faults ensue.
●
Thrashing
≡
a process is busy swapping pages in and out
●
This high paging activity is called thrashing.
9.22
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Thrashing
9.23
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Page-Fault Frequency Scheme
●
Establish “acceptable” page-fault rate
●
If actual rate too low, process loses frame
●
If actual rate too high, process gains frame
9.24
Silberschatz, Galvin and Gagne ©2005
Operating System Concepts – 7
th
Edition, Feb 22, 2005
Prepaging
●
Prepaging
●
To reduce the large number of page faults that occurs at
process startup
●
Prepage all or some of the pages a process will need, before
they are referenced
●
But if prepaged pages are unused, I/O and memory was wasted
End of Chapter 9
